package games;

import games.SquareColor;
//import java.lang.Math.*;
import minmax.GameMove;
import minmax.GameOutcome;
import minmax.GameState;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;

public class KamisadoState implements GameState<KamisadoState.KamisadoMove> {

    private final String boardPattern =
            "BROWN GREEN RED YELLOW PINK PURPLE BLUE ORANGE "
            + "PURPLE BROWN YELLOW BLUE GREEN PINK ORANGE RED "
            + "BLUE YELLOW BROWN PURPLE RED ORANGE PINK GREEN "
            + "YELLOW RED GREEN BROWN ORANGE BLUE PURPLE PINK "
            + "PINK PURPLE BLUE ORANGE BROWN GREEN RED YELLOW "
            + "GREEN PINK ORANGE RED PURPLE BROWN YELLOW BLUE "
            + "RED ORANGE PINK GREEN BLUE YELLOW BROWN PURPLE "
            + "ORANGE BLUE PURPLE PINK YELLOW RED GREEN BROWN";
    protected KamisadoSquare[][] gameBoard = new KamisadoSquare[8][8];
    protected HashMap<Tower, Coordinate> towerPositions;
    private GameOutcome outcome;
    //If the current player is maximizing
    protected boolean player = false;
    protected Stack<KamisadoMove> moves = new Stack<KamisadoMove>();

    public KamisadoState() {
        towerPositions = new HashMap<Tower, Coordinate>(16);
    	readInBoard();
    }
    
    public KamisadoMove getPreviousMove() {
    	if(moves.empty())
    		return null;
    	
    	return moves.peek();
    }
    
    @Override
    public void move(KamisadoMove step) {
        validateMove(step);

        this.gameBoard[step.oldY][step.oldX].setTower(null);
        this.gameBoard[step.y][step.x].setTower(step.tower);
        
        this.towerPositions.put(step.tower, new Coordinate(step.x, step.y));
        this.player = !this.player;
        this.moves.push(step);
    }

    @Override
    public void backtrack() {
    	this.outcome = null;
        this.player = !this.player;
        KamisadoMove step = this.moves.pop();

        this.gameBoard[step.y][step.x].setTower(null);
        this.gameBoard[step.oldY][step.oldX].setTower(step.tower);
        this.towerPositions.put(step.tower, new Coordinate(step.oldX, step.oldY));

    }

    @Override
    public Iterator<KamisadoMove> moves() {
        if (outcome != null) {
            throw new IllegalStateException("Game is finished, no further moves are possible");
        }
        SquareColor colorToMove;
        if (this.moves.empty()) {
            colorToMove = null;
        } else {
            KamisadoMove move = this.moves.peek();
            colorToMove = this.gameBoard[move.y][move.x].getColor();
        }

        return new MoveIterator(player, colorToMove, gameBoard, towerPositions);
    }

    @Override
    public boolean canMove(KamisadoMove move) {
        return isValidMove(move);
    }

    @Override
    public boolean player() {
        return this.player;
    }

    @Override
    public int evaluate(boolean maximize) {
    	boolean player = maximize ? this.player : !this.player;
        if (outcome == null) {
            return heuristic(player);
        } else if (outcome == GameOutcome.Draw) {
            return 0;
        } else {
            boolean winner = outcome.player();
            return player == winner ? Integer.MAX_VALUE - 1 : Integer.MIN_VALUE + 1;
        }
    }

    @Override
    public boolean isFinished() {
        return outcome() != null;
        
    }
    
    @Override
    public GameOutcome outcome() {
    	
        for (int i = 0; i < 8; i++) {
            //min
            Tower minTower = this.gameBoard[0][i].getTower();
            if (minTower != null && !minTower.getPlayer()) {
                this.outcome = GameOutcome.First;
                break;
            }

            //max
            Tower maxTower = this.gameBoard[7][i].getTower();
            if (maxTower != null && maxTower.getPlayer()) {
                this.outcome = GameOutcome.Second;
                break;
            }
        }
        
        if(this.outcome != null) {
        	return this.outcome;
        }
        
        if (deadlockAhead()) {
            if (moves.peek().player()) {
                this.outcome = GameOutcome.First;
            } else {
                this.outcome = GameOutcome.Second;
            }
        }
        
        return this.outcome;
    }
    
    private boolean deadlockAhead() {
        if(moves.empty()){
            return false; //We cannot deadlock on first move
        }
        KamisadoMove move = this.moves.peek();
        Tower origTower = move.tower;
        SquareColor colorToMove = this.gameBoard[move.y][move.x].getColor();
        MoveIterator nextMoves = new MoveIterator(player, colorToMove, gameBoard, towerPositions);
        nextMoves.hasNext();
        int count = 0;
        boolean nextHasNoMoves = nextMoves.noMoves;
        KamisadoMove next = nextMoves.next();
        
        while (next.tower != origTower) {
            if (!nextHasNoMoves) {
                for (int i = 0; i < count; i++) {
                    backtrack();
                }
                return false;
            }

            move(next);
            count++;
            move = this.moves.peek();
            colorToMove = this.gameBoard[move.y][move.x].getColor();
            nextMoves = new MoveIterator(player, colorToMove, gameBoard, towerPositions);
            nextMoves.hasNext();
            nextHasNoMoves = nextMoves.noMoves;
            next = nextMoves.next();
        }

        for (int i = 0; i < count; i++) {
            backtrack();
        }

        return true;
    }

    public Coordinate getCurrentPosition(Tower tower) {
        return towerPositions.get(tower);
    }

    public Tower getTower(int x, int y) {
    	return this.gameBoard[y][x].getTower();
    }
    
    public void readInBoard() {

        String[] cells = this.boardPattern.split(" ");
        for (int i = 0; i < cells.length; i++) {
            int x = i % 8;
            int y = i / 8;
            SquareColor color = SquareColor.valueOf(cells[i]);
            if (y == 0) {
                this.gameBoard[y][x] = new KamisadoSquare(color, new Tower(color, true)); //Maxplayer
                this.towerPositions.put(new Tower(color, true), new Coordinate(x, y));
            } else if (y == 7) {
                this.gameBoard[y][x] = new KamisadoSquare(color, new Tower(color, false)); //Minplayer
                this.towerPositions.put(new Tower(color, false), new Coordinate(x, y));
            } else {
                this.gameBoard[y][x] = new KamisadoSquare(color);
            }
        }
    }

    public KamisadoSquare cell(int x, int y) {
        return this.gameBoard[y][x];
    }

    public boolean isBlocked(int x, int y, boolean player) {
    	int yModifier = 1;
    	boolean straightBlocked = true;
    	boolean rightBlocked = true;
    	boolean leftBlocked = true;
    	if(!player) {
    		yModifier = -1;
    	}
    	if(y > 0 && y < 7) {
    		straightBlocked = gameBoard[y+yModifier][x].getTower() != null;
    	if(x < 7)
    		leftBlocked = gameBoard[y+yModifier][x+1].getTower() != null;
    	if(x > 0)
    		leftBlocked = gameBoard[y+yModifier][x-1].getTower() != null;
    	}
    	
    	return straightBlocked && rightBlocked && leftBlocked;
    }
    
    public boolean isValidMove(KamisadoMove step) {
    	
    	if(gameBoard[step.getY()][step.getX()].getTower() != null)
    		return false;
    	
    	// Check for towers between old and new position.
    	int nextX = 0;
    	if(step.getX() - step.getOldX() > 0)
    		nextX = 1;
    	else if(step.getX() - step.getOldX() < 0)
    		nextX = -1;
    	int x = step.getOldX() + nextX;
    	for(int y = step.getOldY()-1; y >= step.getY(); y--) {
    		if(gameBoard[y][x].getTower() != null)
    			return false;
    		x += nextX;
    	}
    	
    	boolean upperLeft = (step.getOldY()+1 < 8) && 
    			(step.getOldX()-1 >= 0) && 
    			(gameBoard[step.getOldY()+1][step.getOldX()-1].getTower() != null);
    	boolean upperStraight = (step.getOldY()+1 < 8) && 
    			(gameBoard[step.getOldY()+1][step.getOldX()].getTower() != null);
    	boolean upperRight = (step.getOldY()+1 < 8) && 
    			(step.getOldX()+1 < 8) && 
    			(gameBoard[step.getOldY()+1][step.getOldX()+1].getTower() != null);
    	
    	if(step.getOldX() == step.getX() && step.getOldY() == step.getY() && (!upperLeft || !upperStraight || !upperRight))
    		return false; 
    	
    	// Check diagonals
    	boolean diagonal = Math.abs(step.getOldY() - step.getY()) == Math.abs(step.getOldX() - step.getX());
    	// Check straight line
    	boolean straight = step.getX() == step.getOldX();
    	
    	if(!diagonal && !straight)
    		return false;
    	
    	return true;
    }

    @SuppressWarnings("unchecked")
	@Override
    public GameState<KamisadoMove> clone() {
    	try {
			KamisadoState copy = (KamisadoState) super.clone();
			KamisadoSquare[][] board = new KamisadoSquare[8][];
			for (int i = 0; i < 8; i++) {
				board[i] = new KamisadoSquare[8];
				for (int j = 0; j < 8; j++) {
					board[i][j] = copy.gameBoard[i][j].clone();
				}
			}
			copy.gameBoard = board;
			copy.moves = (Stack<KamisadoMove>) copy.moves.clone();
		} catch (CloneNotSupportedException e) {
			throw new AssertionError();
		}
        throw new UnsupportedOperationException("Not supported yet.");
    }

    private void validateMove(KamisadoMove step) {
        if(step == null){
            throw new IllegalArgumentException("Step cannot be null");
        }
    }

    /**
     * In the given heuristic we for each piece of the current player
     * calculate number of enemy pieces that a behind it. Since these
     * pieces cann't block the given piece, we assume that the more 
     * enemy pieces we have on the back the better situation is.
     * We also multiply the weight by distance to the goal.
     * 
     * @param player is the one for who we maximize the outcome
     * @return estimate
     */
    protected int heuristic(boolean player) {
    	// since any move is better then draw, we normalize the result by adding 1
    	int result = 1;
    	// number of enemies, encountered so far
    	int enemies = 0;
    	// distance is a weight of the current piece
    	int distance = 1;
    	// go through the board rows
    	for (int k = 0; k < 8; k++, distance++) {
    		int i = player ? k : 7 - k;
    		int pieces = 0;
    		for (int j = 0; j < 8; j++) {
    			Tower tower = gameBoard[i][j].getTower();
    			if (tower != null) {
    				if (tower.getPlayer() == player) {
    					pieces++;
    				} else {
    					enemies++;
    				}
    			}
    		}
    		result += enemies * pieces * distance;
    	}
        return result;
    }

    public static final class KamisadoMove implements GameMove {

        private final int y;
        private final int x;
        private final int oldX;
        private final int oldY;
        private final Tower tower;

        public KamisadoMove(int x, int y, int oldX, int oldY, Tower tower) {
        	this.y = y;
            this.x = x;
            this.oldX = oldX;
            this.oldY = oldY;
            this.tower = tower;
        }


        @Override
        public boolean player() {
            return this.tower.getPlayer();
        }

        @Override
        public String toString() {
            return "KamisadoMove{" + "y=" + y + ", x=" + x + ", oldX=" + oldX + ", oldY=" + oldY + ", tower=" + tower + '}';
        }

        public int getOldX() {
            return oldX;
        }

        public int getOldY() {
            return oldY;
        }

        public Tower getTower() {
            return tower;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

    private static class MoveIterator implements Iterator<KamisadoState.KamisadoMove> {

        private final boolean player;
        private final SquareColor towerColor;
        private final KamisadoSquare[][] gameBoard;
        private KamisadoMove lastReturnedMove;
        private MoveIterator iterator;
        private Integer x;
        private Integer y;
        private final int yModifier;
        private boolean noMoves = false;
        private HashMap<Tower, Coordinate> towerPositions;
        
        private MoveIterator(boolean player, SquareColor towerColor, KamisadoSquare[][] gameBoard, HashMap<Tower, Coordinate> towerPositions) {
            this.player = player;
            this.towerColor = towerColor;
            this.gameBoard = gameBoard;
            this.yModifier = player ? 1 : -1;
            this.towerPositions = towerPositions;
            
            // Check if we have any moves. If not, we have to stay at the same spot.
            if(towerIsBlocked(towerColor, player)) {
            	this.noMoves = true;
            }
        }
        
        private boolean towerIsBlocked(SquareColor towerColor, boolean player) {
        	if(towerColor != null) {
        		Coordinate c = this.towerPositions.get(new Tower(towerColor, player));
        		int rx = c.X;
        		int ry = c.Y;
        	
        		if(ry == 7 && player || ry == 0 && !player)
        			return false;
			
        		if(rx == 0) {
        			if(this.gameBoard[ry+this.yModifier][rx].getTower() != null && this.gameBoard[ry+this.yModifier][1].getTower() != null)
        				return true;
        		}
        		else if(rx == 7) {
        			if(this.gameBoard[ry+this.yModifier][rx].getTower() != null && this.gameBoard[ry+this.yModifier][6].getTower() != null)
        				return true;
        		}
        		else {
        			if(this.gameBoard[ry+this.yModifier][rx-1].getTower() != null && this.gameBoard[ry+this.yModifier][rx].getTower() != null && this.gameBoard[ry+this.yModifier][rx+1].getTower() != null)
        				return true;
				}
        	}
        	
        	return false;
        }

        @Override
        public boolean hasNext() {
            //Only implemented the computer playing from bottom now
            if (this.towerColor == null) {//startState
                return this.lastReturnedMove == null || !(this.lastReturnedMove.x == 7 && this.lastReturnedMove.y == 1 && this.lastReturnedMove.oldX == 7);
            } else {
                if (x == null) {
                    Coordinate c = towerPositions.get(new Tower(this.towerColor, this.player));
                    if(c != null) {
                    	x = c.X;
                    	y = c.Y;
                    }
                    else {
                    	x = 7;
                    	y = 7;
                    }
                }
                
                if(this.noMoves) {
                	return true;
                }
                
                if (this.lastReturnedMove == null) {
                    return CheckStartState();
                }
                
                if (!(this.lastReturnedMove.x >= this.lastReturnedMove.oldX)) {
                    boolean canMoveLeft = CanMoveLeft();
                    if (canMoveLeft) {
                        return true;
                    }
                }
                
                if (!(this.lastReturnedMove.x > this.lastReturnedMove.oldX)) {
                    boolean canMoveStraight = CanMoveStraight();
                    if (canMoveStraight) {
                        return true;
                    }
                }

                return CanMoveRight();
            }
        }
       
        
        private boolean CheckStartState() {

            if (!CanMoveY()) return false;
            
            // start case
            if (this.x > 0 && this.gameBoard[this.y + yModifier][this.x - 1].getTower() == null) {
                //left
                return true;
            }
            if (this.gameBoard[this.y + yModifier][this.x].getTower() == null) {
                //straight
                return true;
            }
            if (this.x < 7 && this.gameBoard[this.y + yModifier][this.x + 1].getTower() == null) {
                //right
                return true;
            }
            
            return false;
        }

        private boolean CanMoveY() {
            int val = this.y + this.yModifier;
            return val > -1 && val < 8;
        }

        private boolean CanMoveLeft() {
            int rx = this.lastReturnedMove.x;
            int ry = this.lastReturnedMove.y;
            if (!CanMoveY(ry)) return false;

            return rx > 0 && this.gameBoard[ry + this.yModifier][rx - 1].getTower() == null;
        }

        private boolean CanMoveStraight() {
            int rx = this.lastReturnedMove.x;
            int ry = this.lastReturnedMove.y;
            if (rx != this.x) {
                rx = this.x;
                ry = this.y;
            }
            if (!CanMoveY(ry)) return false;

            return this.gameBoard[ry + this.yModifier][rx].getTower() == null;
        }

        private boolean CanMoveRight() {
            int rx = this.lastReturnedMove.x;
            int ry = this.lastReturnedMove.y;
            if (rx <= this.x) {
                rx = this.x;
                ry = this.y;
            }
            if (!CanMoveY(ry)) return false;
            
            return rx < 7 && this.gameBoard[ry + this.yModifier][rx + 1].getTower() == null;
        }

        @Override
        public KamisadoMove next() {
            if (this.towerColor == null) {
                if (lastReturnedMove == null) {
                    if(player){
                    	this.x = this.y = 0;
                    }else{
                        this.x = 0;
                        this.y = 7;
                    }
                    iterator = new MoveIterator(player, SquareColor.ORANGE, gameBoard, towerPositions);
                }

                while (!iterator.hasNext()) {
                    SquareColor color = this.gameBoard[this.y][++this.x].getColor();
                    iterator = new MoveIterator(player, color, gameBoard, towerPositions);
                }


                KamisadoMove move = iterator.next();
                return this.lastReturnedMove = move;

            } else {
            	
            	if(this.noMoves) {
            		this.noMoves = false;
            		return this.lastReturnedMove = getBlockedMove();
            	}
            	
                if (this.lastReturnedMove == null) {
                    return this.lastReturnedMove = getStartMove();
                }

                if (!(this.lastReturnedMove.x >= this.lastReturnedMove.oldX)) {
                    if (CanMoveLeft()) {
                        return this.lastReturnedMove = getLeftMove();
                    }
                }

                if (!(this.lastReturnedMove.x > this.lastReturnedMove.oldX)) {
                    if (CanMoveStraight()) {
                        return this.lastReturnedMove = getStraightMove();
                    }
                }
                
                return this.lastReturnedMove = getRightMove();

            }

        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("iterator is read-only");
        }

        private KamisadoMove getStartMove() {
            if (CanMoveY()){
                if (this.x > 0 && this.gameBoard[this.y + this.yModifier][this.x - 1].getTower() == null) {
                    //left
                    return new KamisadoMove(this.x - 1, this.y + this.yModifier, this.x, this.y, this.gameBoard[this.y][this.x].getTower());
                }
                if (this.gameBoard[this.y + this.yModifier][this.x].getTower() == null) {
                    //straight
                    return new KamisadoMove(this.x, this.y + this.yModifier, this.x, this.y, this.gameBoard[this.y][this.x].getTower());
                }
                if (this.x < 7 && this.gameBoard[this.y + this.yModifier][this.x + 1].getTower() == null) {
                    //right
                    return new KamisadoMove(this.x + 1, this.y + this.yModifier, this.x, this.y, this.gameBoard[this.y][this.x].getTower());
                }
            }

            return new KamisadoMove(this.x, this.y, this.x, this.y, this.gameBoard[this.y][this.x].getTower());
        }
        
        private KamisadoMove getBlockedMove() {
        	Coordinate c = this.towerPositions.get(new Tower(this.towerColor, this.player));
        	return new KamisadoMove(c.X, c.Y, c.X, c.Y, gameBoard[c.Y][c.X].getTower());
        }

        private KamisadoMove getLeftMove() {
            int rx = this.lastReturnedMove.x;
            int ry = this.lastReturnedMove.y;
            return new KamisadoMove(rx - 1, ry + this.yModifier, this.x, this.y, this.gameBoard[this.y][this.x].getTower());
        }

        private KamisadoMove getStraightMove() {
            int rx = this.lastReturnedMove.x;
            int ry = this.lastReturnedMove.y;
            if (rx != this.x) {
                rx = this.x;
                ry = this.y;
            }
            return new KamisadoMove(rx, ry + this.yModifier, this.x, this.y, this.gameBoard[this.y][this.x].getTower());
        }

        private KamisadoMove getRightMove() {
            int rx = this.lastReturnedMove.x;
            int ry = this.lastReturnedMove.y;
            if (rx <= this.x) {
                rx = this.x;
                ry = this.y;
            }
            return new KamisadoMove(rx + 1, ry + this.yModifier, this.x, this.y, this.gameBoard[this.y][this.x].getTower());
        }

        private boolean CanMoveY(int y) {
            int val = y + this.yModifier;
            return val > -1 && val < 8;
        }
    }
}
